package com.gitee.feizns.explore.data_structure.linked_list.singly.mergeKLists;

/**
 * @author feizns
 * @since 2020/3/2
 */
public class MergeKLists2 {

    public static void main(String[] args) {
        println(mergeKLists(new ListNode[]{ create(), create1() }));
    }

    public static ListNode mergeKLists(ListNode[] lists) {
        return mergeKLists(lists, 0, lists.length - 1);
    }

    public static ListNode mergeKLists(ListNode[] lists, int start, int end) {
        if ( start == end )
            return lists[start];
        else if ( start > end )
            return null;
        int mid = (start + end) / 2;
        ListNode n1 = mergeKLists(lists, start, mid);
        ListNode n2 = mergeKLists(lists, mid + 1, end);
        return merge(n1, n2);
    }

    private static ListNode merge(ListNode n1, ListNode n2) {
        if ( n1 == null )
            return n2;
        else if ( n2 == null )
            return n1;
        else if ( n1.val < n2.val ) {
            n1.next = merge(n1.next, n2);
            return n1;
        } else {
            n2.next = merge(n2.next, n1);
            return n2;
        }
    }

    private static ListNode create() {
        ListNode q = new ListNode(0);
        q.next = new ListNode(1);
        q.next.next = new ListNode(2);
        return q;
    }

    private static ListNode create1() {
        ListNode q = new ListNode(0);
        q.next = new ListNode(1);
        q.next.next = new ListNode(2);
        return q;
    }

    private static void println(ListNode re) {
        ListNode t = re;
        while ( t != null ) {
            System.out.print(t.val);
            t = t.next;
        }
    }

}
